package com.mdnote.algorithm;

import com.sun.javafx.sg.prism.NGAmbientLight;

import java.util.Arrays;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/10
 * @description 弗洛伊德算法
 */
public class FloydAlgorithm {

    private static final int INF = 65535;

    public static void main(String[] args) {
        char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int[][] distance = {
                {  0,   5,   7, INF, INF, INF,   2},
                {  5,   0, INF,   9, INF, INF,   3},
                {  7, INF,   0, INF,   8, INF, INF},
                {INF,   9, INF,   0, INF,   4, INF},
                {INF, INF,   8, INF,   0,   5,   4},
                {INF, INF, INF,   4,   5,   0,   6},
                {  2,   3, INF, INF,   4,   6,   0}
        };
        int[][] pre = new int[vertex.length][vertex.length];

        MGraph mGraph = new MGraph(vertex, distance, pre);

        FloydAlgorithm floydAlgorithm = new FloydAlgorithm();
        floydAlgorithm.floyd(mGraph);
        floydAlgorithm.show(mGraph);

        floydAlgorithm.getPath(mGraph, 0, 5);

        for (int[] distanceArr : distance) {
            System.out.println(Arrays.toString(distanceArr));
        }
    }

    /**
     * 显示图
     * @param mGraph 图
     */
    private void show(MGraph mGraph) {
        for (int i = 0; i < mGraph.distance.length; i++) {
            for (int j = 0; j < mGraph.distance[i].length; j++) {
                System.out.println("从" + mGraph.vertex[i] + "到" + mGraph.vertex[j] + "的距离为"  + mGraph.distance[i][j]);
            }
            System.out.println();
        }
    }

    /**
     * 获取对应路径
     * @param mGraph 图
     * @param startIndex 起点
     * @param endIndex 终点
     */
    public void getPath(MGraph mGraph, int startIndex, int endIndex) {
        ;
        int[] paths = mGraph.pre[startIndex];
        do {
            System.out.print(mGraph.vertex[endIndex] + " - ");
            endIndex = paths[endIndex];
        } while (startIndex != endIndex);
        System.out.println(mGraph.vertex[endIndex]);
    }

    private void floyd(MGraph mGraph) {
        // b表示中间节点
        for (int k = 0; k < mGraph.distance.length; k++) {
            // i、j表示中间节点为k的两个顶点
            for (int i = 0; i < mGraph.distance.length; i++) {
                for (int j = 0; j < mGraph.distance.length; j++) {
                    // 计算通过中间顶点的总路程
                    int len = mGraph.distance[i][k] + mGraph.distance[k][j];
                    // 比较一下直接连接比较短还是走中间点比较短
                    if (len < mGraph.distance[i][j]) {
                        // 走中间点比较短
                        mGraph.distance[i][j] = len;
                        // 这个不好理解
                        // mGraph.pre[A][B]的值默认为A，表示A与B连接必须经过A
                        // 现在将i点的与j点之间的连接点设为中间点
                        mGraph.pre[i][j] = mGraph.pre[k][j];
                    }
                }

            }
        }
    }


    private static class MGraph {

        private char[] vertex;
        private int[][] distance;
        private int[][] pre;

        public void setVertex(char[] vertex) {
            this.vertex = vertex;
        }

        public void setDistance(int[][] distance) {
            this.distance = distance;
        }

        public void setPre(int[][] pre) {
            this.pre = pre;
        }

        public MGraph(char[] vertex, int[][] distance, int[][] pre) {
            this.vertex = vertex;
            this.distance = distance;
            this.pre = pre;

            for (int i = 0; i < pre.length; i++) {
                Arrays.fill(pre[i], i);
            }
        }
    }
}
